package class_08;

import java.util.HashSet;
/**
 *  全排列
 * 数据情况： 将所有的数进行全排列，一个不多一个不少
		 *  例如  abc
		 *   abc
		 *   acb
		 *   bac
		 *   bca
		 *   cba
		 *   cab
 *全排列 一个不多一个不少：   
 * 1.有重复的，
 * 		即针对于每一个位置上的，元素，都要进行交换；
 * 			从i开始，和后面的都要交换；
 * 			i=0,时，要和1，2交换
 * 		process(i+1),当i=1,时，要要让，之后的元素进行交换；
 * 2.没有重复的，多了一个hashset这个来控制交换的
 * 			acc   在一个函数里 
 *          ac  都有的情况下，c和a是不会交换的，这种会变化两次，去掉一次 ，比较好，可以去重
 * @author LOGAN
 *
 */
public class Code_04_Print_All_Permutations {

	public static void printAllPermutations1(String str) {
		char[] chs = str.toCharArray();
		process1(chs, 0);
	}
	
	public static void process1(char[] chs, int i) {
		if (i == chs.length) {
			System.out.println(String.valueOf(chs));
			return;
		}
		for (int j = i; j < chs.length; j++) {
			swap(chs, i, j);
			//swap(chs, i, j);
			process1(chs, i + 1);
		}
	}

	public static void printAllPermutations2(String str) {
		char[] chs = str.toCharArray();
		process2(chs, 0);
	}

	public static void process2(char[] chs, int i) {
		if (i == chs.length) {
			System.out.println(String.valueOf(chs));
			return;
		}
		HashSet<Character> set = new HashSet<>();
		for (int j = i; j < chs.length; j++) {
			if (!set.contains(chs[j])) {
				set.add(chs[j]);
				swap(chs, i, j);
				process2(chs, i + 1);
				//swap(chs, i, j);
			}
		}
	}

	public static void swap(char[] chs, int i, int j) {
		char tmp = chs[i];
		chs[i] = chs[j];
		chs[j] = tmp;
	}

	public static void main(String[] args) {
		String test1 = "abc";
		printAllPermutations1(test1);
		System.out.println("======");
		printAllPermutations2(test1);
		System.out.println("======");

		String test2 = "acc";
		printAllPermutations1(test2);
		System.out.println("======");
		printAllPermutations2(test2);
		System.out.println("======");
	}

}
